package day01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ZJX
 * @version 1.0
 * @descption
 * @since 2025/10/11 21:27
 */
public class Z {
    public int removeElement(int[] nums, int val) {
        int ret = 0;
        for (int num : nums) {
            if (num != val) {
                nums[ret] = num;
                ret++;
            }
        }
        return ret;
    }

    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        int ret = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[ret] = nums[i];
                ret++;
            }
        }
        return ret;
    }

    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        i,j,index为 数组下标指针
        int i = m - 1;
        int j = n - 1;
        int index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[index--] = nums1[i--];
            } else {
                nums1[index--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        // 排序 + 双指针
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1, r = nums.length - 1;
            while (r > l) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    ret.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (r > l && nums[l] == nums[l + 1]) l++;
                    while (r > l && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                } else if (sum > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return ret;
    }

    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0, right = n - 1;
        int max = 0;
        while (right > left) {
            int len = right - left;
            int sum = Math.min(height[left], height[right]) * len;
            max = Math.max(max, sum);
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return max;
    }

    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j++;
            }
        }
    }

    public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1 || nums[0] > nums[1]) {
            return 0;
        }
        int left = 0, right = n - 1;
        while (right > left) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (right >= left) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[mid] >= nums[left]) {
//                左半部分有序
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
//                右半部分有序
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

            }
        }
        return -1;
    }
}

